
package solvers.spanningTree;

import controller.solvers.ISolver;
import controller.solvers.UnappropriateTypeException;
import java.util.Vector;
import java.util.logging.Level;
import java.util.logging.Logger;
import jgf.Arc;
import jgf.IGraph;
import jgf.Node;
import jgf.exceptions.arc.BadArcInsertionException;
import jgf.lists.Graph;

/**
 *
 * @author Marcos Garcia Ortega <thiamath@gmail.com>
 */
public class SpanningTree implements ISolver{

	private int steps;
	private boolean finish;
	private Graph input;

	private Graph t;
	private Vector<Graph> unmergedT;
	private Vector<Arc> s;


	public SpanningTree(){
		steps = 0;
		finish = false;
		t = new Graph();
		unmergedT = new Vector<Graph>();
		s = new Vector<Arc>();
	}

	public IGraph solve(IGraph input) throws UnappropriateTypeException {
		if(!(input instanceof Graph)) // Type check
			throw new UnappropriateTypeException("This solver should be called only with a graph as target");
		
		this.input = new Graph((Graph)input);

		while(!finish){
			t = (Graph) step();
		}

		return t;
	}

	public IGraph step() {

		if(steps == 0){ // Initialization
			t = new Graph(input);
			s = t.getArcList();
			t.getArcTree().clear();
			steps++;
			return t;
		}

		Arc e = argMin("cost", s); // e := minimum cost arc in s
		s.remove(e); // s := s\{e}

		if(!makesCycle(unmergedT, e)){ // if T U {e} not contains cycles
			try {
				Arc e2 = new Arc(t.getNode(e.getFrom().getId()), t.getNode(e.getTo().getId()), e.getLabel(), e.getAttributes());
				t.insertArc(e2); // T := T U {e}
			} catch (BadArcInsertionException ex) {
				Logger.getLogger(SpanningTree.class.getName()).log(Level.SEVERE, null, ex);
			}
		}

		if(s.isEmpty())
			finish = true;

		return t;
	}

	private Arc argMin(String attributeName, Vector<Arc> arcs){
		Arc ret = arcs.firstElement();
		for (Arc arc : arcs) {
			if(arc.getAttribute(attributeName).getValue() > ret.getAttribute(attributeName).getValue())
				ret = arc;
		}
		return ret;
	}

	private boolean makesCycle(Vector<Graph> trees, Arc e) {
		int graphIndexFrom = -1, graphIndexTo = -1;

		for (int i = 0; i < trees.size(); i++) {
			Graph loopGraph = trees.elementAt(i);
			Node from = loopGraph.getNode(e.getFrom().getId());
			Node to = loopGraph.getNode(e.getTo().getId());
			if(from.getLinkedArcs().isEmpty() && to.getLinkedArcs().isEmpty()){
				// The arc e not connect to any tree at index i;
			}if(from.getLinkedArcs().isEmpty() && !to.getLinkedArcs().isEmpty()){
				graphIndexTo = i; // The From node of e is conected into the tree of index i
			}if(!from.getLinkedArcs().isEmpty() && to.getLinkedArcs().isEmpty()){
				graphIndexFrom = i; // The To node of e is conected into the tree of index i
			}if(!from.getLinkedArcs().isEmpty() && !to.getLinkedArcs().isEmpty()){
				return true; // The From and To of e are on the same tree ot t == cycle
			}
		}
		if(graphIndexFrom == -1 && graphIndexTo == -1){ // If e not connects to any graph in t
			// Create a new tree in t with e.
			Graph nuovo = new Graph(input);
			nuovo.getArcTree().clear();
			try {
				Arc e2 = new Arc(nuovo.getNode(e.getFrom().getId()), nuovo.getNode(e.getTo().getId()), e.getLabel(), e.getAttributes());
				nuovo.insertArc(e2);
			} catch (BadArcInsertionException ex) {
				Logger.getLogger(SpanningTree.class.getName()).log(Level.SEVERE, null, ex);
			}
			trees.add(nuovo);
			return false;
		}
		if(graphIndexFrom == -1){ // If e just connects with the graph of index graphIndexTo
			// Insert e into the graph of index graphIndexTo.
			try {
				Graph tree = trees.get(graphIndexTo);
				Arc e2 = new Arc(tree.getNode(e.getFrom().getId()), tree.getNode(e.getTo().getId()), e.getLabel(), e.getAttributes());
				// If e just connects with the graph of index graphIndexTo
				// Insert e into the graph of index graphIndexTo.
				trees.get(graphIndexTo).insertArc(e2);
			} catch (BadArcInsertionException ex) {
				Logger.getLogger(SpanningTree.class.getName()).log(Level.SEVERE, null, ex);
			}
			return false;
		}
		if(graphIndexTo == -1){ // If e just connects with the graph of index graphIndexFrom
			// Insert e into the graph of index graphIndexFrom.
			try {
				Graph tree = trees.get(graphIndexFrom);
				Arc e2 = new Arc(tree.getNode(e.getFrom().getId()), tree.getNode(e.getTo().getId()), e.getLabel(), e.getAttributes());
				// If e just connects with the graph of index graphIndexTo
				// Insert e into the graph of index graphIndexTo.
				trees.get(graphIndexFrom).insertArc(e2);
			} catch (BadArcInsertionException ex) {
				Logger.getLogger(SpanningTree.class.getName()).log(Level.SEVERE, null, ex);
			}
			return false;
		}
		if(graphIndexFrom != graphIndexTo){ // If e connects two graphs in t
			// Merge them and add e.
			Graph g1 = trees.elementAt(graphIndexFrom);
			Graph g2 = trees.elementAt(graphIndexTo);
			Graph merged = (Graph)GraphTools.merge(g1, g2);
			try {
				Arc e2 = new Arc(merged.getNode(e.getFrom().getId()), merged.getNode(e.getTo().getId()), e.getLabel(), e.getAttributes());
				merged.insertArc(e2);
			} catch (BadArcInsertionException ex) {
				Logger.getLogger(SpanningTree.class.getName()).log(Level.SEVERE, null, ex);
			}
			trees.remove(g1);
			trees.remove(g2);
			trees.add(merged);
			return false;
		}
		// If none of the previous conditions are true, means that e produces a cycle.
		return true;
	}
}
